
 

\documentclass[11pt]{article}
\newtheorem{define}{Definition}
%\newcommand{\F}{{\mathbb{F}}}
%\usepackage{psfig}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{graphicx}
\usepackage{algorithm}%

\usepackage{algpseudocode}%

\oddsidemargin=0.15in
\evensidemargin=0.15in
\topmargin=-.5in
\textheight=9in
\textwidth=6.25in


\newcommand{\eps}{\epsilon}


\begin{document}

\input{preamble.tex}

%{lecture number}{lecture date}{Elena Grigorescu}{Your name}
\lecture{4}{Aug 30, 2012}{Elena Grigorescu}{Pinar Yanardag Delul}
\section{ Estimating the number of connected components and minimum spanning tree}

In {\em Lecture 3}, we showed a test for connectivity of graphs and today we'll see how to estimate the number of connected components of a graph in  constant time. In particular, we will focus on the following problems:
 \begin{itemize}
 \item Estimating the number of connected components
\item Estimating minimum spanning tree weight
\end{itemize}

These results are due to Chazelle et al \cite{CRT05}. Recall what we said about testing connectivity in the last lecture. It reduced to showing that if we have a graph that needs to be modified in many places in order to obtain a connected graph then it must have many connected components of small size. And then we showed that we can find these connected components with high probability by sampling random vertices and visiting the components that they belonged to in a BFS manner.  We'll use a similar idea here as well and we are going to be estimating the number of connected components by estimating sizes of random connected components.

\section{An additive approximation algorithm}
Recall that an $\alpha$-additive approximation algorithm is an algorithm for an optimization problem that outputs a solution within $\alpha$ of the optimum solution. That is, if $OPT$ is the value of the solution to the optimization problem, an $\alpha$-additive approximation algorithm outputs a value $v$ such that $|v-OPT| \leq \alpha$. 

\begin{theorem}\label{thm:numcon}
There $\exists$ a randomized algorithm that given $\epsilon$ and a graph $G(V,E),$ with $|V|=n$ outputs an $\epsilon n $-additive approximation to the number of connected components of $G$, w.p. $2/3$. That is, if $C$ is the number of connected components of $G$, w.p. $2/3$ the algorithm outputs $v$ s.t. $|v-C|\leq \eps n$.
\end{theorem} 

Notice that this algorithm is useful when $G$ has many connected components i.e. $\Theta(n)$. Recall from last lecture that if a graph has many connected components then it must have many connected components of small size (say,  of size $2/\eps.$ See Figure \ref{fig:1}) At a very high level, the algorithm will use the size of the small components to estimate $C$, the number of connected components.


\begin{figure}\label{fig:1}
\centering
\includegraphics[height=.2\textheight]{cc.png}\\
\caption{Size of the small connected components is $\frac{2}{\epsilon}$}.
\label{the-label-for-cross-referencing}
\end{figure}

In what follows we will prove Theorem \ref{thm:numcon}.

For a vertex $v$ let $n_{v} = \#$ of vertices in $C(v)$ (where $C(v)$ denotes the connected component where $v$ lies).


We are going to use $n_{v}$ in order to estimate the number of connected components. We can make two simple observations about $n_{v}$:

\begin{observation}  
$\sum_{v\in C_{i}}\frac{1}{n_v} = 1$ where $C_{i}$ is the connected component $i$. This is true since $|C_i|=n_v$ for all $v\in C_i$.

\end{observation}



\begin{observation}  
$\sum_{v\in V}\frac{1}{n_v} = C$.  (This is true since each component contributes exactly $1$ to the sum.)
\end{observation}  



Now we have a way to compute the number of connected components in some sort of a local way (i.e. $n_{v}$ gives us some local information about $v$). But notice that if we try to calculate exactly the number of connected components by using this quantity, it will take $O(n^2)$ time (for each vertex, we have to look all of its neighbors).  Instead, we can try to estimate $n_{v}$ for a random sample and hope to get something close to the number of connected components.
 
 
If we pick a random sample $S$ of vertices and compute the estimate $\sum_{v\in S} \frac{1}{n_v}$, notice that if $n_{v}$ is large, then $\frac{1}{n_{v}}$ is small, and so it has a small contribution to the sum. In our algorithm we will see that is enough to round the number of vertices inside a large component to a fixed threshold (in our case $\frac{2}{\epsilon}$). 

\begin{definition}
Let ${\hat n}_v=\min\{n_v, 2/\eps\}.$ That is,
$\hat{n}_{v} = \begin{cases}
n_{v} & \text{ if } v \in \text{connected component of size} < \frac{2}{\epsilon}
 \\
\frac{2}{\epsilon} & \text{ otherwise }
\end{cases}
$

\end{definition}

In what follows we will denote a component of size $<\eps/2$ a {\em small} component.

\begin{lemma}\label{lem:hat1}
$0\leq \frac{1}{{\hat n}_v}-\frac{1}{n_v}< \eps/2.$
\end{lemma}
\begin{proof}

If $v$ is in small component then $\frac{1}{{\hat n}_v}-\frac{1}{n_v}=0$, else $0<\frac{1}{{\hat n}_v}-\frac{1}{n_v}=\frac{\eps}{2}-\frac{1}{n_v}<\eps/2.$
\end{proof}


We can now define an estimate for $C$ using the rounding above.

\begin{definition}
Let $\hat{C} = \sum_{v\in V}\frac{1}{\hat{n_{v}}}$\\
\end{definition}


\begin{lemma}\label{lem:hat2}
$|C-\hat{C}| < \frac{\epsilon n}{2}$
\end{lemma}

\begin{proof}
Using Lemma \ref{lem:hat1} we have 
$0\leq \sum_{v\in V} \frac{1}{{\hat n}_v}-\frac{1}{n_v}\leq \eps n/2$ and hence $|\hat{C} - C| \leq \eps n/2$

\end{proof}


We are now ready to see an algorithm that estimates $C$ by estimating $\hat C$, which in turn can be achieved by sampling a bunch of vertices and computing  ${\hat n}_{v}$ for each sampled vertex $v$. In order to compute ${\hat n}_{v}$ we will search the connected component of $v$ and if we found that it is strictly smaller than $\frac{2}{\epsilon}$ we set ${\hat n}_{v}$ be the actual size of the component, otherwise we set ${\hat n}_v=\frac{2}{\epsilon}$. Then we will sum up the values $\frac{1}{{\hat n}_v}$, take the average and multiply by $n$ and that will be our output (our estimate).
 
\begin{algorithm} 
\caption{Algorithm that, given $G$ and $\eps$ estimates the number of connected components in $G$.
}\label{euclid}
\begin{algorithmic}[1]
\State Pick $s = O(\frac{1}{\epsilon^2})$ vertices in a sample $S = \{v_{1}, \ldots, v_{s}\}$
\State Run BFS around each $v_{i}$ until the search reaches at most $\frac{2}{\eps}$ vertices.  
\State For each such $v\in S$ set $\hat{n_{v}}$ = number of vertices in $v$'s component if it is  $< \frac{2}{\epsilon}$ and set $\hat{n_{v}} = \frac{2}{\epsilon}$ otherwise
\State Output $\left(\frac{1}{s}\sum_{v\in S} \frac{1}{\hat{n_{v}}}\right) n = C'$

\end{algorithmic}
\end{algorithm}


We claim that the output of Algorithm 1 is a very good estimate of the number of connected components:
\begin{theorem}
With probability $2/3$ (over its randomness), Algorithm 1 outputs ${C}'$ such that $|{C}'- C| < \epsilon n$, and runs in time $O(\frac{1}{\epsilon^4})$. 
\end{theorem}

{\bf Runtime analysis}  Running BFS takes $O((\frac{2}{\epsilon})^2)$ time  and this is essentially the complexity of the algorithm (this step can be done even in linear time if we know a bound $d$ on the degrees), but here we will just use a rough estimate).

We will need to analyze the deviation from expectation of the output estimate. We have previously seen a few examples of how to use the Chernoff bound in order to achieve this step. We will use the bound again in our analysis and we recall it next.


\begin{theorem}[Chernoff] Let random variables $X_{1}, \dots, X_{s} \in [0, 1]$ be independent and identically distributed and let $X = \sum_{i=1}X_{i}$. Then 
$Pr\left [ |X-E[X]| > \frac{\epsilon s}{2} \right ] < e^{-\frac{\epsilon^{2}}{8}s} =  e^{-\Omega(\epsilon^{2}s)}$
\end{theorem}

\begin{lemma}\label{lem:c'}
$Pr[|{C}' - \hat{C}| > \frac{\epsilon}{2}n] < \frac{1}{3}$

\end{lemma}



\begin{proof}
Let $X_{i}=\frac{1}{\hat{n_{v_{i}}}}$ be a random variable for the quantity $\frac{1}{\hat{n_{v_{i}}}}$  associated to the $i$th sampled vertex where $1 \leq i \leq s$.
Then 
$E[X_{i}] = \frac{1}{n} \sum_{v \in V} \frac{1}{\hat{n_{v}}} = \frac{\hat{C}}{n},$
 for every $i$.
Let $X = \sum_{i=1}^s X_{i}$, then $E[X] = E[\sum_{i=1}^s X_i]=\sum_{i=1}^s E[X_i]=s \frac{\hat{C}}{n}$. So $X=\sum_{i=1}^{s}\frac{1}{\hat{n_{v_{i}}}}$ is a random variable for the value that we output (the algorithm actually outputs $C'=\frac{n}{s}X$). We want to understand how far $C'=\frac{n}{s} X$ is from its expected value (i.e. $\frac{n}{s} E[X]=\hat C$). 
For this we apply Chernoff's bound
and obtain
$$Pr[|X -E[X]| \geq \frac{\epsilon}{2}s] < e^{-\Omega ( \epsilon^2 s )} < \frac{1}{3},$$  for $s=O(\frac{1}{\eps^2}).$
So
$$Pr[|X\frac{n}{s} - \frac{s}{n}\hat{C}\frac{n}{s}| > \frac{\epsilon}{2}s\frac{n}{s} ] < \frac{1}{3},$$ and finally 

$Pr[|{C}'  - \hat{C}| > \frac{\epsilon n}{2}] < \frac{1}{3}$, concluding the proof.

\end{proof}

To summarize, the algorithm above outputs an $\eps n/2$-additive approximation to ${\hat C}$, with probability $2/3$. We will next show that this is also an $\eps n$-additive approximation to $C$, the number of connected components. 

\begin{proof}[of Theorem \ref{thm:numcon}]
By Lemma \ref{lem:c'} we know that $Pr[|C'-{\hat C}|>\eps n/2]<1/3$ and by Lemma \ref{lem:hat2} $|{\hat C}-C|<\eps n/2$, and recall that we want to show that $Pr[|C'-C|>\eps n]<1/3$.

Note that if $|C'-C|>\eps n$ then $\eps n<|C'-C|\leq |C'-{\hat C}|+|{\hat C}-C|$ and so $|C'-{\hat C}|>\eps n/2$, which, by Lemma happens w.p. $1/3$. It follows that $Pr[|C'-C|>\eps n]<1/3$ which concludes the proof.

\end{proof}



What if we want a smaller probability of error, that is we want that that to increase our confidence to $1-\delta$, where $\delta $ is can be set arbitrarily small? 

\begin{observation}\label{obs:1}
If we pick $s = O(\frac{1}{\epsilon^2}log \frac{1}{\delta})$ samples in the above algorithm we have that 
$$Pr[|C' - \hat{C}| > \frac{\epsilon}{2}n ] <e^{-\Omega ( \epsilon^2 s )} <\delta,$$
\end{observation}

\section{Estimating the Minimum spanning tree weight}
 
Now, we will see how to estimate the MST of a weighted connected graph. 
We will use the algorithm for estimating the number of connected components from the previous section as a subroutine(in fact the one where we pick $s = O(\frac{1}{\epsilon^2}log \frac{1}{\delta})$ samples. 

For a given undirected graph $G$ and $n$ vertices and edge-weights  $W = \{w_{e}| e \in E(G)\}$ are a given set of e where $w_{e} \in \{1, 2, \dots, w\}$. The goal is to estimate the MST (a spanning tree of minimum weight), $w(MST(G))$ 
 i.e to output an estimate ${\hat w}(MST(G))$ s.t $|{\hat w}(MST(G))-w(MST(G))|<\eps n$.

In order to do it in sublinear time, we will try to express the weight of the MST as a function of some local quantities, and those local quantities will be the sizes of connected components of some carefully chosen subgraphs. We will look at subgraphs of $G$ and count the number of connected components in these subgraphs and we are going to use estimates of these to estimate $w(MST)$.


Let $G_{1} = $ subgraph of G with edges of weight $\leq 1$. Let $C_1$ be the number of connected components in $C_1$.

Let $T$ be some $MST(G)$ and we want to estimate how many edges in T have weight strictly greater than 1. 

We can now make a few observations. 
\begin{enumerate}
\item $T$ cannot have an edge of weigth $>1$ between the vertices of a connected component of $G_1$ since that would result in a cycle. So in order to get $T$ we must add edges of wt $>1$ between disconnected components of $C_1$.  
\item  Each time an edge is added to $C_1$ (greedily, maintaining the tree spanning structure) the number of disconnected components in the new graph decreases by exactly $1$.
\end{enumerate}

Therefore, we have proved that the $\#$ of edges of weight $>1$ in $T$ is exactly $C_1-1$.


More generally,
define another graph $G_{i}$ which is the subgraph of $G$ with only weight $\leq i$, where $i\leq w$.


By the same argument as above, the number of edges of weight $> i$ in $T$ is exactly $C_{i} -1$,\\

Observe that this is true even for $i=0$ as the number of components of $G_0$  is $n$ and the number of edges in $T$ is $n-1$.

\begin{lemma}

w(MST(G)) = $\sum_{ 0 \leq i \leq w} (C_{i} -1)$

\end{lemma}


\begin{proof}
Let $N_i$ be the number of edges of weight $i$ in $T$. Then

\begin{eqnarray*}
w(MST) &=&\sum_{ i = 1}^w i \cdot N_{i}\\
       &=&\sum (1 + 1 + \ldots + 1) N_{i}\\
       &=& \sum_{ i = 1}^w N_{i} + \sum_{i = 2}^w  N_{i}  +\ldots + \sum_{ i = w-1}^w N_{i}+\sum_{ i = w}^w N_{i}\\
       &=& \sum_{ i = 0}^w C_{i} -1,
\end{eqnarray*}
where the last identity uses the claim proved above that  $\sum_{i = j}^w  N_{j}=C_j-1$.
\end{proof}

This is gives us a more  local way to express the weight of the MST. From here, we will use the previous lemmas for estimating the number of connected components for each of the $G_{i}'s$.

\begin{algorithm} 
\caption{Algorithm that, given $G$ and $\eps$ and set of weights $W$ estimates MST(G).}\label{alg:2}
\begin{algorithmic}[1]
\State For $i=1, ..w$ compute ${\hat C}_i$, an approximate to the number of connected components of $G_i$ by running Algorithm \ref{euclid} on the graph $G_i$, with  $\eps'=\eps/w$ and confidence parameter $\delta=\frac{1}{3w}$.
\State Output ${\hat w}(MST)=-w+\sum_{i=1}^{w-1} {\hat C}_i$
\end{algorithmic}
\end{algorithm}  

{\bf Analysis}  If all estimates ${\hat C_i}$ are within an additive error $\frac{\eps}{w} n$, i.e. $|{\hat C}_i-C_i|\leq \frac{\eps}{w} n$ then
$$|\sum_i {\hat C}_i-C_i|=|{\hat w}(MST)-w(MST)|\leq \sum_{i=0}^{w-1} |{\hat C}_i-C_i|\leq w\cdot \frac{\eps}{w}n=\eps n.$$
So, with $O(\frac{1}{\eps^2} \log \frac{w}{\eps})$ samples, for each $i$ $Pr[|{\hat C}_i-C_i|\geq \frac{\eps}{w}n]<\frac{1}{3w}.$
By a union bound $$Pr[ \mbox{ one of the estimates is bad }]\leq w\cdot \frac{1}{3w}=1/3.$$


\bibliographystyle{plain}
\bibliography{biblio}
\end{document}





























